package listnode.question;

/**
 * 题目:
     给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * 示例:
    输入：head = [1,2,3,4,5], n = 2
    输出：[1,2,3,5]
 * 注意:
    要删除一个结点，要求指向被删除的上一个结点
 * 时间复杂度: O(n)
 * 空间复杂度: O(1)
 */

import listnode.ListNode;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class RemoveNthFromEnd {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //创建一个虚拟头结点
        ListNode dumyHead=new ListNode();
        dumyHead.next=head;

        //定义一个快指针，一个慢指针
        //找到倒数第n个结点，可以先让快指针移动n步
        //然后快慢指针一起向前移动，直到慢指针移到null
        //但删除结点要找的是前一个结点，所以快指针先动n+1步
        ListNode fast=dumyHead;
        ListNode slow=dumyHead;
        for(int i=0;i<=n;i++){// 注意：我们想要移动n+1步，所以循环n+1次，即i从0到n（包括n）一共n+1次
            fast=fast.next;
        }

        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }

        //删除结点
        slow.next=slow.next.next;

        return dumyHead.next;


    }
}